/*****************************************************
Copyright (C) 2020. All rights reserved.
File name     ：TreapTree.c
Version       ：v1.0
Author        ：zhengqijun
Date          ：2020-04-18
Function List ：
Description   ：AA-Tree
******************************************************/

#include "TreapTree.h"
#include <stdlib.h>  // for malloc
#include "FatalError.h"
#include "LinkedStack.h"
#include "LinkedQueue.h"

#define Infinity 65535

struct TreapNode {
    ElementType Element;
    TreapTree   Left;
    TreapTree   Right;
    int         Priority;
};

// Static Function Lists
static int Random(void);
static Position SingleRotateWithLeft(Position K2);
static Position SingleRotateWithRight(Position K1);

// Static Variable Lists
static Position NullNode = NULL;  /* Needs initialization */

TreapTree Initialize(void) {
    if (NullNode == NULL) {
        NullNode = (TreapTree)malloc(sizeof(struct TreapNode));
        if (NullNode == NULL) {
            FatalError("Out of space!!!");
        }

        NullNode->Left = NullNode;
        NullNode->Right = NullNode;
        NullNode->Priority = Infinity;
    }

    return NullNode;
}

TreapTree MakeEmpty(TreapTree T) {
    if (T != NullNode) {
        MakeEmpty(T->Left);
        MakeEmpty(T->Right);
        free(T);
    }

    return NullNode;
}

int IsEmpty(TreapTree T) {
    return (T == NULL) || (T == NullNode);
}

// Non-recursive implement
Position Find(ElementType X, TreapTree T) {
    while (T != NullNode) {
        if (X < T->Element) {
            T = T->Left;
        } else if (X > T->Element) {
            T = T->Right;
        } else {
            break;
        }
    }

    return T;
}

// Non-recursive implement
Position FindMin(TreapTree T) {
    if (T != NullNode) {
        while (T->Left != NullNode) {
            T = T->Left;
        }
    }

    return T;
}

// Non-recursive implement
Position FindMax(TreapTree T) {
    if (T != NullNode) {
        while (T->Right != NullNode) {
            T = T->Right;
        }
    }

    return T;
}

/* Use ANSI C random number generator for simplicity */
static int Random(void) {
    return rand() - 1;
}

/* This function can be called only if K2 has a left child */
/* Perform a rotate between a node (K2) and its left child */
/* Update heights, then return new root */
static Position SingleRotateWithLeft(Position K2) {
    Position K1;

    K1 = K2->Left;
    K2->Left = K1->Right;
    K1->Right = K2;

    return K1;  /* New root */
}

/* This function can be called only if K1 has a right child */
/* Perform a rotate between a node (K1) and its right child */
/* Update heights, then return new root */
static Position SingleRotateWithRight(Position K1) {
    Position K2;

    K2 = K1->Right;
    K1->Right = K2->Left;
    K2->Left = K1;

    return K2;  /* New root */
}

TreapTree Insert(ElementType X, TreapTree T) {
    if (T == NullNode) {
        /* Create and return a one-node tree */
        T = (TreapTree)malloc(sizeof(struct TreapNode));
        if (T == NULL) {
            FatalError("Out of space!!!");
        } else {
            T->Element = X;
            T->Priority = Random();
            T->Left = NullNode;
            T->Right = NullNode;
        }
    } else if (X < T->Element) {
        T->Left = Insert(X, T->Left);
        if (T->Left->Priority < T->Priority) {
            T = SingleRotateWithLeft(T);
        }
    } else if (X > T->Element) {
        T->Right = Insert(X, T->Right);
        if (T->Right->Priority < T->Priority) {
            T = SingleRotateWithRight(T);
        }
    }
    /* Otherwise it's a duplicate; do nothing */

    return T;  /* Do not forget this line!! */
}

TreapTree Delete(ElementType X, TreapTree T) {
    if (T != NullNode) {
        if (X < T->Element) {
            T->Left = Delete(X, T->Left);
        } else if (X > T->Element) {
            T->Right = Delete(X, T->Right);
        } else {
            /* Match found */
            if (T->Left->Priority < T->Right->Priority) {
                T = SingleRotateWithLeft(T);
            } else {
                T = SingleRotateWithRight(T);
            }

            if (T != NullNode) {
                /* Continue on down */
                T = Delete(X, T);
            } else {
                /* At a leaf */
                free(T->Left);
                T->Left = NullNode;
            }
        }
    }

    return T;
}

Position Left(Position P) {
    return P->Left;
}

Position Right(Position P) {
    return P->Right;
}

ElementType Retrieve(Position P) {
    return P->Element;
}

// Recursive implement
// void PreorderTraversal(TreapTree T) {
//     if (T != NullNode) {
//         printf("%d ", T->Element);
//         PreorderTraversal(T->Left);
//         PreorderTraversal(T->Right);
//     }
// }

// Non-recursive implement
void PreorderTraversal(TreapTree T) {
    if (T != NullNode) {
        LinkedStack S;
        Position P;

        S = CreateStack();

        P = T;
        while (P != NullNode || !IsEmptyStack(S)) {
            while (P != NullNode) {
                printf("%d ", P->Element);
                Push(P, S);
                P = P->Left;
            }

            P = TopAndPop(S);
            P = P->Right;
        }
    }
}

// Recursive implement
// void InorderTraversal(TreapTree T) {
//     if (T != NullNode) {
//         InorderTraversal(T->Left);
//         printf("%d ", T->Element);
//         InorderTraversal(T->Right);
//     }
// }

// Non-recursive implement
void InorderTraversal(TreapTree T) {
    if (T != NullNode) {
        LinkedStack S;
        Position P;

        S = CreateStack();

        P = T;
        while (P != NullNode || !IsEmptyStack(S)) {
            while (P != NullNode) {
                Push(P, S);
                P = P->Left;
            }

            P = TopAndPop(S);
            printf("%d ", P->Element);
            P = P->Right;
        }
    }
}

// Recursive implement
// void PostorderTraversal(TreapTree T) {
//     if (T != NullNode) {
//         PostorderTraversal(T->Left);
//         PostorderTraversal(T->Right);
//         printf("%d ", T->Element);
//     }
// }

// Non-recursive implement
void PostorderTraversal(TreapTree T) {
    if (T != NullNode) {
        LinkedStack S;
        Position Pre;
        Position Cur;

        S = CreateStack();

        Cur = T;
        Pre = NullNode;
        while (Cur != NullNode || !IsEmptyStack(S)) {
            if (Cur != NullNode) {
                Push(Cur, S);
                Cur = Cur->Left;
            } else {
                Cur = Top(S);
                if (Cur->Right != NullNode && Cur->Right != Pre) {
                    Cur = Cur->Right;
                } else {
                    Pop(S);
                    printf("%d ", Cur->Element);
                    Pre = Cur;
                    Cur = NullNode;
                }
            }
        }
    }
}

void LevelorderTraversal(TreapTree T) {
    if (T != NullNode) {
        LinkedQueue Q;

        Q = CreateQueue();

        EnQueue(T, Q);

        while (!IsEmptyQueue(Q)) {
            if (Front(Q)->Left != NullNode) {
                EnQueue(Front(Q)->Left, Q);
            }

            if (Front(Q)->Right != NullNode) {
                EnQueue(Front(Q)->Right, Q);
            }

            printf("%d ", Retrieve(FrontAndDequeue(Q)));
        }
    }
}

// EOF

